#!/usr/bin/env python
# encoding: utf-8
# @Time : 2020/4/22 17:48 
# @Author : 能量咖啡豆 
# @File : 53.py
# @desc : leetcode 53 最大子序和

'''
扫描发O(N),如果current为负数时，重置current为num[i],扫描获取
'''

def solution1(nums):
    sum = nums[0]
    current = nums[0]
    for i in range(1,len(nums)):
        if current < 0:
            current = nums[i]
        else:
            current += nums[i]
        if current > sum:
            sum = current
    return sum

'''
动态规划解法 
'''
#def solution2(nums):


if __name__ == "__main__":
    print("hello")
    nums = [-2,4,-3,1]
    sum = nums[0]
    current = nums[0]
    for i in range(1,len(nums)):
        if current < 0 :
            current = nums[i]
        else:
            current += nums[i]
        if current > sum:
            sum = current

    print(sum)